#leetcode题目155：最小栈
#难度：中等
#时间复杂度：O(1)
#空间复杂度：O(n)
#方法：栈

class MinStack:
    #ai方法
    # def __init__(self):
    #     self.stack = []
    #     self.min_stack = []

    # def push(self, val: int) -> None:
    #     self.stack.append(val)
    #     if not self.min_stack or val <= self.min_stack[-1]:
    #         self.min_stack.append(val)

    # def pop(self) -> None:
    #     if self.stack.pop() == self.min_stack[-1]:
    #         self.min_stack.pop()

    # def top(self) -> int:
    #     return self.stack[-1]

    # def getMin(self) -> int:
    #     return self.min_stack[-1]

    def __init__(self):
        """
        初始化栈
        """
        self.stack = []  # 主栈，存储所有元素
        self.min_stack = []  # 辅助栈，存储每个位置对应的最小值

        #Python的 list 已经足够：
        # list.append() 相当于 Deque.push()
        # list.pop() 相当于 Deque.pop()
        # list[-1] 相当于 Deque.peek()
    
    def push(self, val: int) -> None:
        """
        将元素val推入栈中
        :param val: 要推入的元素
        """
        # 总是将元素推入主栈
        self.stack.append(val)
        
        # 处理最小值栈
        if not self.min_stack:
            # 如果最小值栈为空，当前元素就是最小值
            self.min_stack.append(val)
        else:
            # 如果最小值栈不为空，比较当前元素和栈顶元素
            current_min = self.min_stack[-1]
            if current_min < val:
                # 如果当前最小值小于新元素，保持原最小值
                self.min_stack.append(current_min)
            else:
                # 如果新元素小于等于当前最小值，更新最小值
                self.min_stack.append(val)

    def pop(self) -> None:
        """
        删除栈顶的元素
        """
        # 同时从两个栈中弹出元素
        self.stack.pop()
        self.min_stack.pop()
    
    def top(self) -> int:
        """
        获取栈顶元素
        :return: 栈顶元素
        """
        return self.stack[-1]
    
    def getMin(self) -> int:
        """
        检索栈中的最小元素
        :return: 栈中的最小元素
        """
        return self.min_stack[-1]

#测试数据
# 输入：
# ["MinStack","push","push","push","getMin","pop","top","getMin"]
# [[],[-2],[0],[-3],[],[],[],[]]

# 输出：
# [null,null,null,null,-3,null,0,-2]

# 解释：
# MinStack minStack = new MinStack();
# minStack.push(-2);
# minStack.push(0);
# minStack.push(-3);
# minStack.getMin();   --> 返回 -3.
# minStack.pop();
# minStack.top();      --> 返回 0.
# minStack.getMin();   --> 返回 -2.
minStack = MinStack()
print(minStack.__init__())
print(minStack.push(-2))
print(minStack.push(0))
print(minStack.push(-3))
print(minStack.getMin())
print(minStack.pop())
print(minStack.top())
print(minStack.getMin())